#include<stdio.h>

//插入排序
void insertion_sort(int unsorted_array[], int num_elements){
    int temp,i,j;
    for (i = 1; i < num_elements; i++) {
        temp = unsorted_array[i];
        for (j = i-1; j >= 0 && unsorted_array[j]>temp; j--) {
            unsorted_array[j+1]=unsorted_array[j];
        }
        unsorted_array[j+1] = temp;
    }
}

//快速排序
void quick_sort(int unsorted_array[], int num_elements){
    for (int i = 0; i < num_elements; i++) {
        int start = 0,end = num_elements-1;
        while (start<end){
            int base = unsorted_array[i];
            while (unsorted_array[start]<base){
                start++;
            }
            while (unsorted_array[end]>base){
                end--;
            }
            int temp=unsorted_array[start];
            unsorted_array[start]=unsorted_array[end];
            unsorted_array[end]=temp;
        }
    }
}
void AdjustMaxHeap(int N[], int target, int n) {
    int i = target;
    int j = 2 * i + 1;
    int temp = N[i];
    while(j <= n) {
        if(j < n && N[j] < N[j + 1]) {	// 找出左右孩子的最大值
            j++;
        }
        if(temp < N[j]) {	// 不满足大根堆则交换元素值
            N[i] = N[j];
            i = j;
            j = 2 * j + 1;
        }
        else {
            break;
        }
    }
    N[i] = temp;
}
void heap_sort(int unsorted_array[], int num_elements){
    int i;
    // 构造大根堆，元素从 0 开始
    for(i = num_elements/2 - 1; i >=0; i--) {
        AdjustMaxHeap(unsorted_array, i, num_elements - 1);
    }
    int temp;
    // 取堆顶元素，重新构造新堆
    for(i = num_elements - 1; i > 0; i--) {
        temp = unsorted_array[0];
        unsorted_array[0] = unsorted_array[i];
        unsorted_array[i] = temp;
        AdjustMaxHeap(unsorted_array, 0, i - 1);
    }
}

void main() {
    int a[] = {1,9,8,7,6,5,0,2,3,4};
    insertion_sort(a, 10);
    for(int i=0; i<10; i++) {
        printf("%d ", a[i]);
    }
    printf("\n"); //  此时应该看到输出为 0 1 2 3 4 5 6 7 8 9
    int c[] = {1,5,10,4,3,6,7,9,2,8};
    quick_sort(c,10);
    for (int i = 0; i < 10; i++) {
        printf("%d ",c[i]);
    }
    printf("\n");
    int d[] = {56, 62, 41, 10, 87, 69, 15, 5, 75, 0};
    heap_sort(d,10);
    for (int i = 0; i < 10; i++) {
        printf("%d ",d[i]);
    }
    // 定义 int c[], int d[]，并初始化，用于测试quick_sort和heap_sort
}